package leetcode_300;

import java.util.Arrays;

public class PerfectSquares_279_ {
	int dp[];
	boolean judge[];
	public static void main(String[] args) {
		PerfectSquares_279_ test=new PerfectSquares_279_();
		System.out.println(test.numSquares(12));

	}
	/**
	 * describe:四平方和定理 AC 100%
	 * 2018年6月28日 下午2:09:10
	 */
	public int numSquares(int n) {
		while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        for (int a = 0; a * a <= n; ++a) {
            int b = (int)Math.sqrt(n - a * a);
            if (a * a + b * b == n) {
                if(a*b==0)
                	return 1;
                return 2;
            }
        }
        return 3;
    }
	
	/**
	 * describe:动态规划  AC 93%
	 * 2018年6月27日 下午5:38:42
	 */
	public int numSquares1(int n) {
	       this.dp=new int[n+1];
	       dp[0]=0;
	       Arrays.fill(dp, Integer.MAX_VALUE);
	       for(int i=0;i<=n;++i)
	    	   for(int j=1;i+j*j<=n;++j) {
	    		   dp[i+j*j]=Math.min(dp[i+j*j], dp[i]+1);//因为j*j就是平方数
	    	   }
	      
	       return dp[n];
	    }
	
	/**
	 * describe:贪心算法  思想错误 每次并非先从最近平方数中找
	 * 2018年6月28日 下午2:47:11
	 */
	public int numSquares2(int n) {
	       this.judge=new boolean[n+1];
	       for(int i=1;i<=Math.sqrt(n);++i) {//把平方数填上
	    	   judge[i*i]=true;
	       }
	       int res=0;
	       while(n>0) {
	    	   int now=help(n);
	    	   n-=now;
	    	   res+=1;
	       }
	       return res;
	    }
	
	
	public int help(int n) {
		for(int i=n;i>=0;--i) {
			if(judge[i])
				return i;
		}
		return -1;
	}
}
